'''
二叉树的前序、中序、后序遍历的2种实现方式：递归和迭代
测试方法自己构造出二叉树 并测试6个功能
'''

'''
三种方式下的递归实现：
二叉树的前序、中序、后序遍历（递归方式），核心思路是 **“分治思想”+“固定访问顺序”：以当前节点为中心，将遍历任务拆解为 “访问当前节点” 和 “递归遍历左子树、右子树” 两部分，
三者（前序、中序、后序）的唯一区别是“访问当前节点的时机不同”**，而左子树的遍历始终优先于右子树（因二叉树左、右子树有明确区分）。
1. 前序遍历（Pre-order Traversal）：“根 → 左 → 右”
核心思路：先访问当前根节点，再递归遍历左子树，最后递归遍历右子树。
第一步：直接处理（访问 / 输出）当前节点（“根” 优先）；
第二步：若当前节点有左子树，递归对左子树执行前序遍历；
第三步：若当前节点有右子树，递归对右子树执行前序遍历；
终止条件：递归到 “空节点” 时，直接返回（无操作）。
简单理解：“先拿当前节点的内容，再依次去左、右子树里‘先拿内容再找子树’”。

2. 中序遍历（In-order Traversal）：“左 → 根 → 右”
核心思路：先递归遍历左子树，再访问当前根节点，最后递归遍历右子树。
第一步：若当前节点有左子树，先递归对左子树执行中序遍历（“左” 优先，先把左子树遍历完）；
第二步：处理（访问 / 输出）当前节点（左子树遍历完后，再拿当前节点内容）；
第三步：若当前节点有右子树，递归对右子树执行中序遍历；
终止条件：递归到 “空节点” 时，直接返回。
简单理解：“先把左子树‘挖到底’，再拿当前节点内容，最后去右子树里‘挖左、拿内容、找右’”。（注：中序遍历二叉搜索树时，输出结果是有序的，这是其重要特性）。

3. 后序遍历（Post-order Traversal）：“左 → 右 → 根”
核心思路：先递归遍历左子树，再递归遍历右子树，最后访问当前根节点。
第一步：若当前节点有左子树，先递归对左子树执行后序遍历（“左” 优先）；
第二步：若当前节点有右子树，再递归对右子树执行后序遍历（左子树完了再处理右子树）；
第三步：处理（访问 / 输出）当前节点（左、右子树都遍历完后，最后拿当前节点内容）；
终止条件：递归到 “空节点” 时，直接返回。
简单理解：“先把左、右子树都‘挖到底遍历完’，最后才拿当前节点的内容”。（注：后序遍历常用于 “删除二叉树”“计算节点高度” 等场景，因需先处理子节点再处理父节点）。

本质上，递归的 “重复性” 让我们无需手动控制遍历路径 —— 只需定义 “当前节点该做什么、子树该何时遍历”，剩下的交给递归自动拆解执行即可。

--------------------------------------------------

三种方式下的迭代实现：
二叉树的前序、中序、后序遍历的迭代方式，核心思想是用栈（Stack）模拟递归过程—— 通过手动维护栈来记录遍历路径，替代递归中系统自动维护的调用栈，
从而实现非递归的遍历逻辑。三者的差异主要体现在节点入栈、出栈的时机和处理顺序上：

1. 前序遍历（根→左→右）：“先处理根，再压右、后压左”
核心思路：
栈用于记录待访问的节点，每次先处理（访问）当前根节点，再按 “右子树→左子树” 的顺序将子节点压入栈（因栈是 “后进先出”，左子树会先被弹出处理）。
步骤：
1)初始化栈，将根节点入栈；
2)当栈不为空时，弹出栈顶节点，立即访问（输出）；
3)若该节点有右子节点，先将右子节点入栈；
4)若该节点有左子节点，再将左子节点入栈（保证左子树先于右子树被处理）；
5)重复步骤 2)-4)，直到栈为空。

2. 中序遍历（左→根→右）：“先压左到底，弹出时处理根，再处理右”
核心思路：
栈用于记录 “未处理根节点” 的路径，需先一路向左深入，将所有左子节点入栈，直到最左叶子节点；然后弹出栈顶节点（此时左子树已处理完），访问该节点（根），再转向其右子树重复上述过程。
步骤：
1)初始化栈，定义指针从根节点开始；
2)若指针不为空或栈不为空：
    ①若指针不为空，将当前节点入栈，指针移向其左子树（继续深入左子树）；
    ②若指针为空，弹出栈顶节点，访问该节点（此时左子树已处理完），指针移向其右子树（开始处理右子树）；
重复步骤 2)，直到指针为空且栈为空。

3. 后序遍历（左→右→根）：“标记法区分是否首次入栈，二次弹出时处理根”
核心思路：
难点在于 “根节点需在左右子树都处理完后才访问”，因此需要用标记（如特殊符号或布尔值）区分节点是 “首次入栈” 还是 “左右子树已处理完”。首次入栈时不访问，仅标记后入栈；二次弹出（左右子树处理完）时才访问。
步骤（以 “标记法” 为例）：
1)初始化栈，将根节点（带 “未处理” 标记）入栈；
2)当栈不为空时，弹出栈顶节点：
    ①若节点未标记：标记为 “已处理” 后重新入栈，再依次将其右子树（未标记）、左子树（未标记）入栈（保证左→右→根的顺序）；
    ②若节点已标记：访问该节点（此时左右子树已处理完）；
3)重复步骤 2)，直到栈为空。
（另一种思路：利用前序遍历 “根→右→左” 的结果反转，得到后序 “左→右→根”，本质是通过调整入栈顺序间接实现。）

总结：迭代法的核心共性与差异
共性：
均用栈模拟递归路径，通过控制节点入栈、出栈的时机，实现 “左子树优先于右子树” 的遍历规则。
差异：
前序：出栈即访问（根优先），子节点按 “右→左” 入栈；
中序：左子树到底后出栈才访问（根在左后），依赖指针控制入栈深度；
后序：需标记节点状态（或反转前序结果），确保根在左右子树之后访问。
迭代法的本质是 “将递归的隐性栈操作显性化”，通过手动管理栈来控制遍历顺序，避免递归可能带来的栈溢出问题（尤其对深度极大的树）。

'''
#树节点的数据结构的定义
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 前序遍历 递归 根 -> 左 -> 右
def preorder_recursive(root):
    result = []
    '''
    在这些例子中，将 dfs 定义在外层方法的内部是比较合适的。因为 dfs 只用于辅助 外层方法 完成递归遍历，不需要被外部访问；同时它需要访问并修改 result 变量，
    嵌套定义能充分利用闭包的特性，使代码简洁且逻辑清晰。而如果将 dfs 提到外部，会增加参数传递的麻烦，也可能导致命名空间的混乱。
    '''
    def dfs(node):
        if node:
            result.append(node.val)  ##根左右的顺序关系的体现
            dfs(node.left)
            dfs(node.right)
    dfs(root)
    return result

'''
1. 前序遍历 迭代法实现（根→左→右）：“先处理根，再压右、后压左”
核心思路：
栈用于记录待访问的节点，每次先处理（访问/输出）当前根节点，再按 “右子树→左子树” 的顺序将子节点压入栈（因栈是 “后进先出”，左子树会先被弹出处理）。
步骤：
1)初始化栈，将根节点入栈；
2)当栈不为空时，弹出栈顶节点，立即按题目要求访问（比如：输出）；
3)若该节点有右子节点，先将右子节点入栈；一个节点入栈就行，不需要一直探测到底；
4)若该节点有左子节点，再将左子节点入栈（保证左子树先于右子树被处理）；一个节点入栈就行，不需要一直探测到底；
5)重复步骤 2)-4)，直到栈为空。
'''
def preorder_iterative(root):
    result = []
    #根节点为空时，直接返回空集合result
    if not root:
        return result
    #根节点不为空时 根节点入栈  这步不在循环里  根节点直接入栈
    stack = [root]
    #栈不为空时 while循环执行
    while stack:
        #弹出当前栈顶节点
        node = stack.pop()
        #按题目要求 访问弹出的栈顶节点，本次是append搜集起来,便于最后输出
        result.append(node.val)
        #若被弹出的节点有右子节点
        if node.right:
            #右子节点入栈
            stack.append(node.right)
        # 若被弹出的节点有左子节点
        if node.left:
            # 左子节点入栈
            stack.append(node.left)
    return result


#----------------------------------------------------------------------
'''
中序遍历 递归实现 “左 → 根 → 右”
核心思路：先递归遍历左子树，再访问当前根节点，最后递归遍历右子树。
第一步：若当前节点有左子树，先递归对左子树执行中序遍历（“左” 优先，先把左子树遍历完）；
第二步：处理（访问 / 输出）当前节点（左子树遍历完后，再拿当前节点内容）；
第三步：若当前节点有右子树，递归对右子树执行中序遍历；
终止条件：递归到 “空节点” 时，直接返回。
简单理解：“先把左子树‘挖到底’，再拿当前节点内容，最后去右子树里‘挖左、拿内容、找右’”。
（注：中序遍历二叉搜索树时，输出结果是有序的，这是其重要特性）
'''
def inorder_recursive(root):
    result = []
    def dfs(node):
        #若节点非空
        if node:
            #对当前节点的左子树进行递归方式下的中序处理
            dfs(node.left)    ##左根右的顺序关系的体现
            result.append(node.val)
            dfs(node.right)
    dfs(root)
    return result


'''
2. 中序遍历  迭代法 （左→根→右）：“先压左到底，弹出时处理根，再处理右”
核心思路：
栈用于记录 “未处理根节点” 的路径，需先一路向左深入，将所有左子节点入栈，直到最左叶子节点，
然后弹出栈顶节点（此时左子树已处理完），访问该节点（根），再转向其右子树重复上述过程。
具体步骤：
1)初始化栈，定义指针从根节点开始；
2)若指针不为空或栈不为空：
    情况1:若指针不为空，将当前节点入栈，指针移向其左子树（继续深入左子树），即：只要左子树一直有，则已知深挖左子树，不管别的
    情况2:若指针为空，弹出栈顶节点，访问该节点（此时左子树已处理完），指针移向其右子树（开始处理右子树）
重复步骤2)，直到指针为空且栈为空
'''
def inorder_iterative(root):
    result = []
    ##初始化栈
    stack = []
    ##定义指针(current)指向root元素即根元素
    current = root
    # 若指针不为空或栈不为空 注意：python中，空集合也是False，"空"都是False
    while current or stack:
        #若指针不为空
        while current:
            ##将当前节点入栈
            stack.append(current)
            #指针移向其左子树（继续深入左子树）
            current = current.left
        #若指针为空 弹出栈顶节点  pop() 不带参数时，默认移除并返回列表最后一个元素（时间复杂度 O (1)）
        #在 Python 中，pop() 是列表（list）的一个方法，作用是移除并返回列表的最后一个元素（即栈顶元素，因为栈是 “后进先出” 的数据结构，通常用列表的尾部模拟栈顶）。
        #若传入索引（如 pop(0)），则移除并返回对应索引的元素（但此时时间复杂度为 O (n)，不推荐用于模拟栈操作）
        #pop:Remove and return item at index (default last).
        current = stack.pop()
        #访问该节点（此时左子树已处理完）
        result.append(current.val)
        #指针移向其右子树（开始处理右子树）
        current = current.right
    return result

#----------------------------------------------------------------------

# 后序遍历 递归 左 -> 右 -> 根
def postorder_recursive(root):
    result = []
    def dfs(node):
        if node:
            dfs(node.left)  ##左右根的顺序关系的体现
            dfs(node.right)
            result.append(node.val)
    dfs(root)
    return result
'''
后序遍历 迭代法（左→右→根）：“标记法区分是否首次入栈，二次弹出时才处理根”
核心思路：
难点在于 “根节点需在左右子树都处理完后才访问”，因此需要用标记（如特殊符号或布尔值）区分节点是 “首次入栈” 还是 “左右子树已处理完”。
首次入栈时不访问，仅标记后入栈；二次弹出（左右子树处理完）时才访问。
步骤（以 “标记法” 为例）：
1)初始化栈，将根节点（带 “未处理” 标记）入栈
2)当栈不为空时，弹出栈顶节点：
    ①若节点未标记：标记为 “已处理” 后重新入栈，再依次将其右子树（未标记）、左子树（未标记）入栈（保证左→右→根的顺序）；
    ②若节点已标记：访问该节点（此时左右子树已处理完）；
3)重复步骤 2)，直到栈为空。
（另一种思路：利用前序遍历 “根→右→左” 的结果反转，得到后序 “左→右→根”，本质是通过调整入栈顺序间接实现。）
'''
#后序遍历 迭代法
def postorder_iterative(root):
    result = []
    if not root:
        return result
    #初始化栈，将根节点（带 “未处理” 标记）入栈，这里list中每一个元素都是一个元组
    stack = [(root, False)]
    #当栈不为空时
    while stack:
        #只要栈不为空，直接弹出栈顶节点 注意：只是弹出，并不代表加入result结果集合里
        node, visited = stack.pop()
        #若节点已经标记
        if visited:
            #访问该节点
            result.append(node.val)
        #若节点未标记
        else:
            #则将该节点标记为已访问，重新入栈(直接的已经pop出，不用担心)
            stack.append((node, True))
            #再依次将该节点的右子树(未标记)、左子树(未标记)入栈
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))
    return result


# 测试
if __name__ == "__main__":
    # 构建测试二叉树
    #       1
    #      / \
    #     2   3
    #    / \   \
    #   4   5   6
    #  /
    # 7

    #只传入了一个参数 7，这个参数会按照位置匹配到第一个参数 val 上; 对于 left 和 right 参数，因为没有传入对应的参数，所以会使用它们的默认值 None
    #n7是TraeeNode类型
    n7 = TreeNode(7)
    n4 = TreeNode(4, n7)
    n5 = TreeNode(5)
    n2 = TreeNode(2, n4, n5)
    n6 = TreeNode(6)
    n3 = TreeNode(3, None, n6)
    root = TreeNode(1, n2, n3)

    print("前序递归:", preorder_recursive(root))  # [1,2,4,7,5,3,6]
    print("前序迭代:", preorder_iterative(root))
    print("中序递归:", inorder_recursive(root))  # [7,4,2,5,1,3,6]
    print("中序迭代:", inorder_iterative(root))
    print("后序递归:", postorder_recursive(root))  # [7,4,5,2,6,3,1]
    print("后序迭代:", postorder_iterative(root))
